using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
namespace Leet
{
    class P022
    {
        public static void Run()
        {
            var solution = new Solution();
            for (int i = 1; i <= 8; i++)
            {
                Profiler.Run(solution.GenerateParenthesis, i, ShowResult);
            }
        }

        public static void ShowResult(IList<string> result)
        {
            var sb = new StringBuilder();
            foreach (var str in result)
            {
                sb.Append("\" " + str + "\", ");
            }
            Console.WriteLine(sb);
        }
        public class Solution
        {
            public IList<string> GenerateParenthesis(int n)
            {
                if (n == 0)
                    return new List<string>();
                var all = GenerateAllPattern(n*2);
                var filterList = new List<string>(1 << n);
                foreach (var str in all)
                {
                    if (IsMatched(str))
                    {
                        filterList.Add(str);
                    }
                }

                return filterList;
            }

            //生成所有
            public IList<string> GenerateAllPattern(int n)
            {
                if (n == 0)
                    return null;

                if (n == 1)
                {
                    return new List<string> { "(", ")" };
                }

                var preList = GenerateAllPattern(n - 1);
                var newList = new List<string>(preList.Count * 2);
                foreach (var str in preList)
                {
                    newList.Add(str + "(");
                    newList.Add(str + ")");
                }

                return newList;
            }

            //检测可用
            public bool IsMatched(string str)
            {
                int count = 0;
                for (int i = 0; i < str.Length; i++)
                {
                    var c = str[i];
                    if (c == '(')
                    {
                        count++;
                    }
                    if (c == ')')
                    {
                        count--;
                        if (count < 0)
                            return false;
                    }
                }

                return count == 0;
            }

        }
    }
}